/**
 *  @file FindIntersectin.c
 *  @desc 实现两个升序双向链表的交集提取功能：
 *        - 找出两个链表中相同的数据项（交集元素）
 *        - 直接在链表 la 中保留交集元素，非交集部分将被释放
 *        - 不改变链表 lb 的结构
 *  @author WangBlue(wangjiping596@gmail.com)
 *  @date 2025-07-22 16:22
 *  @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>

// ------------------------- 结构体定义 -------------------------

/**
 * @brief 双向链表结点结构体
 */
typedef struct node {
    int data;               ///< 数据域
    struct node *next;      ///< 指向下一个节点
    struct node *pre;       ///< 指向上一个节点
} node, *link;

// ------------------------- 基础操作函数 -------------------------

/**
 * @brief 创建一个带数据的新结点
 * @param value 要存储的值
 * @return 成功返回新结点指针，失败返回 NULL
 */
link createNode(int value) {
    link newNode = (link) malloc(sizeof(node));
    if (newNode == NULL) return NULL;

    newNode->next = NULL;
    newNode->pre  = NULL;
    newNode->data = value;
    return newNode;
}

/**
 * @brief 初始化一个带头结点的空链表
 * @param head 指向链表头指针的地址
 */
void initNode(link *head) {
    link newNode = (link) malloc(sizeof(node));
    if (newNode == NULL) return;

    newNode->next = NULL;
    newNode->pre  = NULL;
    newNode->data = 0;  // 头结点不存储有效数据
    *head = newNode;
}

// ------------------------- 插入操作 -------------------------

/**
 * @brief 头插法，将新节点插入链表开头（头结点之后）
 * @param head 链表头指针
 * @param value 插入的数据
 */
void istHead(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;

    newNode->next = head->next;
    newNode->pre  = head;

    if (head->next != NULL)
        head->next->pre = newNode;

    head->next = newNode;
}

/**
 * @brief 尾插法，将新节点插入链表末尾
 * @param head 链表头指针
 * @param value 插入的数据
 */
void istTail(link head, int value) {
    link cur = head;
    while (cur->next != NULL) {
        cur = cur->next;
    }

    link newNode = createNode(value);
    if (newNode == NULL) return;

    cur->next = newNode;
    newNode->pre = cur;
}

// ------------------------- 打印链表 -------------------------

/**
 * @brief 从头到尾正向打印链表内容（跳过头结点）
 * @param head 链表头指针
 */
void printList(link head) {
    if (head == NULL || head->next == NULL) return;

    link cur = head->next;
    while (cur != NULL) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

// ------------------------- 删除操作 -------------------------

/**
 * @brief 删除链表中指定逻辑位置的结点（从 1 开始计数）
 * @param head 链表头指针
 * @param pos 要删除的位置（从 1 开始）
 */
void delByPos(link head, int pos) {
    if (head == NULL || head->next == NULL) return;

    int idx = 1;
    link cur = head->next;

    while (cur != NULL && idx < pos) {
        cur = cur->next;
        idx++;
    }

    if (cur == NULL) return;

    if (cur->pre != NULL)
        cur->pre->next = cur->next;

    if (cur->next != NULL)
        cur->next->pre = cur->pre;

    free(cur);
}

/**
 * @brief 在第 pos 个位置之前插入数据
 * @param head 链表头指针
 * @param value 要插入的值
 * @param pos 插入的位置（从 1 开始）
 */
void insertByPos(link head, int value, int pos) {
    if (head == NULL || pos < 1) return;

    link cur = head;
    int idx = 0;
    while (cur != NULL && idx < pos - 1) {
        cur = cur->next;
        idx++;
    }

    if (cur == NULL) return;

    link newNode = createNode(value);
    if (newNode == NULL) return;

    newNode->next = cur->next;
    newNode->pre  = cur;

    if (cur->next != NULL)
        cur->next->pre = newNode;

    cur->next = newNode;
}

// ------------------------- 查找交集元素 -------------------------

/**
 * @brief 查找两个升序链表的交集元素，并保留在链表 la 中，释放其余节点
 * @param la 第一个链表（结果保留在此链表中）
 * @param lb 第二个链表（不修改其结构）
 */
void findIntersection(link la, link lb) {
    if (la == NULL || la->next == NULL || lb == NULL || lb->next == NULL) return;

    link pa = la->next;
    link pb = lb->next;

    while (pa != NULL && pb != NULL) {
        if (pa->data == pb->data) {
            // 是交集元素，保留，双指针前进
            pa = pa->next;
            pb = pb->next;
        } else if (pa->data < pb->data) {
            // 非交集元素，删除该结点
            link temp = pa->next;
            pa->pre->next = pa->next;
            if (pa->next != NULL)
                pa->next->pre = pa->pre;
            free(pa);
            pa = temp;
        } else {
            // 当前 pb 小，继续往后找匹配
            pb = pb->next;
        }
    }

    // 清理 la 中剩余非交集元素（因为 pb 已到末尾）
    while (pa != NULL) {
        link temp = pa->next;
        pa->pre->next = pa->next;
        if (pa->next != NULL)
            pa->next->pre = pa->pre;
        free(pa);
        pa = temp;
    }

    // 如果 la 为空，修复头结点指向
    if (la->next != NULL && la->next->pre != la) {
        la->next = NULL;
    }
}

// ------------------------- 主函数 -------------------------

int main() {
    link head = NULL;
    initNode(&head);
    istTail(head, 1);
    istTail(head, 2);
    istTail(head, 3);

    link head1 = NULL;
    initNode(&head1);
    istTail(head1, 2);
    istTail(head1, 3);
    istTail(head1, 4);

    printf("----------------------------------------------\n");
    findIntersection(head1, head);  // 原地修改 head，只保留 2 和 3
    printList(head1);

    return 0;
}
